package leetcode.editor.cn.dsa11_sort;
// 特殊的二进制序列

import java.util.ArrayList;
import java.util.List;

public class SpecialBinaryString761_1 {
    public static void main(String[] args) {
        Solution solution = new SpecialBinaryString761_1().new Solution();
        System.out.println(solution.makeLargestSpecial("11011000"));
        //11100100
        System.out.println(solution.makeLargestSpecial("1110110000"));
        //1111001000
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String makeLargestSpecial(String S) {
            // 结束条件
            if (S.length() <= 2) {
                return S;
            }
            // 1.找出满足要求的特殊子串
            // 存储连续的特殊子串，符合要求的字符串必定是1开头0结尾的
            List<String> list = new ArrayList<>();
            int countOne = 0; // 存放1、0的数量差
            int start = 0; // 符合规则特殊子串的起始位置
            int len = S.length();
            // 从前往后遍历查找，以start开头是否存在符合要求子串
            for (int i = 0; i < len; i++) {
                countOne += S.charAt(i) == '1' ? 1 : -1; // 计算1、0的数量差
                if (countOne == 0) { // 表示找到一个特殊子串
                    // 对特殊字串去掉头尾1、0然后递归求解字典序最大
                    String result = makeLargestSpecial(S.substring(start + 1, i));
                    // 将这个特殊子串放到当前list中
                    list.add("1" + result + "0");
                    // 下一个特殊子串的开始位置
                    start = i + 1;
                }
            }
            String[] arr = list.toArray(new String[list.size()]);
            // 2.对数组中的连续子串进行快速排序
            quickSort(arr, 0, arr.length - 1);
            StringBuilder sb = new StringBuilder();
            // 3.排序后的连续子串，逆序（字典序最大）拼接成字符串
            for (int i = arr.length - 1; i >= 0; i--) {
                sb.append(arr[i]);
            }
            return sb.toString(); // 返回排序后的字符串
        }

        // 快速排序
        public void quickSort(String[] arr, int low, int high) {
            int i = low, j = high;
            String temp = arr[i];
            while (i < j) {
                while (i < j && arr[j].compareTo(temp) >= 0) j--;
                if (i < j) arr[i++] = arr[j];
                while (i < j && arr[i].compareTo(temp) <= 0) i++;
                if (i < j) arr[j--] = arr[i];
            }
            arr[i] = temp;
            if (low < i - 1) quickSort(arr, low, i - 1);
            if (high > i + 1) quickSort(arr, i + 1, high);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}